package leetcode.d_200_299;

import java.util.*;

public class P207 {
    class Solution {
        public  boolean canFinish(int numCourses, int[][]prerequisites) {
            //定义入度数组，索引处（课程号）对应入度，比如课程0的入度为0
            int[] inDegree = new int[numCourses];
            //定义map数组，key课程号，value：依赖key的课程号，比如key为1，依赖的value为3，4
            Map<Integer, List<Integer>> map = new HashMap<>();

            //遍历依赖关系表；在入度数组对应索引处++
            for (int i=0; i<prerequisites.length; i++) {
                int course = prerequisites[i][0];
                int preCourse = prerequisites[i][1];
                inDegree[course]++;
                map.putIfAbsent(preCourse, new ArrayList<>());
                map.get(preCourse).add(course);
            }

            //新建列表，把入度为0的课放进来
            Queue<Integer> queue = new LinkedList<>();
            for (int i=0; i<inDegree.length; i++) {
                if (inDegree[i] == 0) {
                    queue.offer(i);
                }
            }

            while (!queue.isEmpty()) {
                //弹出已选课程，在map找到依赖它的课程，在入度数组--
               int course = queue.poll();
                numCourses--;
                for (int nextCourse : map.getOrDefault(course, new ArrayList<>())) {
                    if (--inDegree[nextCourse] == 0) {
                        queue.offer(nextCourse);
                    }
                }
            }

            return numCourses == 0;
        }
    }

    public static void main(String[] args) {
        P207.Solution solution = new P207().new Solution();
        int numCourses = 2;
        int[][] prerequisites = {{1,0}};
        System.out.println(solution.canFinish(numCourses, prerequisites));
    }
}
